package core.demo;

import core.obj.Sort;
import javafx.util.Pair;

import java.util.Comparator;

public class QuickSort<T> extends Sort<T> {
    public QuickSort(Comparable<T>[] arr) {
        super(arr);
    }

    @Override
    public void sort() {
        int left=0;
        int right=arr.length-1;
        sort(arr,left,right);
    }
    private void sort(Comparable<T>[] arr,int left,int right)//support method
    {
        if (left>right)//递归结束
        {
            return;
        }
        Comparable<T> base=arr[left];//保留基准数
        int i=left;
        int j=right;
        while (i!=j)
        {
            while(arr[j].compareTo((T)base)>=0 && i<j)
            {
                pointers.addElement(new Pair<>(i, j));
                j--;
                if (i<j) {
                    pointers.addElement(new Pair<>(i, j));
                }
            }
            while(arr[i].compareTo((T)base)<=0 && i<j)
            {
                pointers.addElement(new Pair<>(i,j));
                i++;
                if (i<j) {
                    pointers.addElement(new Pair<>(i, j));
                }
            }
            //当i<j时，进入交换部分
            if(i<j) {
                process.addElement(new Pair<>(i,j));
                swap(arr,i,j);
            }
        }
        if (left!=i) {
            process.addElement(new Pair<>(left, i));
        }
        swap(arr,left,i);//和首元素换
        sort(arr,left,j-1);
        sort(arr,i+1,right);
    }
    private void swap(Comparable<T>[] arr,int x,int y)
    {
        Comparable<T> temp;
        temp=arr[x];
        arr[x]=arr[y];
        arr[y]=temp;
    }
}
